#include <catch2/catch.hpp>

#include <memory>

#include "solution.hpp"

/*
Input: root = [1,null,2,3] Output : [1,3,2]
Input: root = []           Output : []
Input: root = [1]          Output : [1]
Input: root = [1,2]        Output : [2,1]
Input: root = [1,null,2]   Output : [1,2]
*/

TEST_CASE("094_binary_tree_inorder_traversal", "[094]")
{
    std::array< std::unique_ptr<TreeNode>, 4 > nodes {
        nullptr,
        std::make_unique<TreeNode>(1),
        std::make_unique<TreeNode>(2),
        std::make_unique<TreeNode>(3),
    };

    SECTION("example 1")
    {
        auto root = nodes[1].get();
        root->right = nodes[2].get();
        root->right->left = nodes[3].get();
        CHECK(Solution().inorderTraversal(root) == std::vector{1,3,2});
        CHECK(Solution().inorderTraversal2(root) == std::vector{1,3,2});
    }

    SECTION("example 2")
    {
        auto root = nodes[0].get();
        CHECK(Solution().inorderTraversal(root).empty());
        CHECK(Solution().inorderTraversal2(root).empty());
    }

    SECTION("example 3")
    {
        auto root = nodes[1].get();
        CHECK(Solution().inorderTraversal(root) == std::vector{1});
        CHECK(Solution().inorderTraversal2(root) == std::vector{1});
    }

    SECTION("example 4")
    {
        auto root = nodes[1].get();
        root->left = nodes[2].get();
        CHECK(Solution().inorderTraversal(root) == std::vector{2,1});
        CHECK(Solution().inorderTraversal2(root) == std::vector{2,1});
    }

    SECTION("example 5")
    {
        auto root = nodes[1].get();
        root->right = nodes[2].get();
        CHECK(Solution().inorderTraversal(root) == std::vector{1,2});
        CHECK(Solution().inorderTraversal2(root) == std::vector{1,2});
    }
}
